package pro.softzhang.algo.lc100;

import pro.softzhang.algo.common.TreeNode;

public class LC124_BinaryTreeMaximumPathSum {
    public static void main(String[] args) {

    }

    static class Solution {
        public int maxPathSum(TreeNode root) {
            int[] max = {Integer.MIN_VALUE};
            doMaxPathSum(root, max);
            return max[0];
        }

        private int doMaxPathSum(TreeNode root, int[] max) {
            if(root == null) {
                return 0;
            }

            int[] maxLeft = {Integer.MIN_VALUE};
            int left = Math.max(0, doMaxPathSum(root.left, maxLeft));

            int[] maxRight = {Integer.MIN_VALUE};
            int right = Math.max(0, doMaxPathSum(root.right, maxRight));

            max[0] = Math.max(maxLeft[0], maxRight[0]);
            max[0] = Math.max(max[0], left + right + root.val);

            return root.val + Math.max(left, right);
        }
    }
}
